|
|
st有两种
讲得很清楚的博客
O(nmlogm) - O(n)
O(nmlognlogm) - O(1)
这题是求正方形，可以O(nmlogt) - O(1)
O(nm)的单调队列
写错是因为变量名打错！！
luogu2216 [HAOI2007]理想的正方形
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1008;
int n,m,t;
int a[N][N],maxi[N][N][8],mini[N][N][8];
int len,ans=INT_MAX;
int main()
{
n=read();m=read();t=read();
memset(mini,0x3f,sizeof(maxi));
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
maxi[i][j][0]=mini[i][j][0]=a[i][j]=read();
}
}
for(int k=1;(1<<k)<=t;++k){
for(int i=1;i+(1<<k)-1<=n;++i){
for(int j=1;j+(1<<k)-1<=m;++j){
maxi[i][j][k]=max(max(maxi[i][j][k-1],maxi[i+(1<<(k-1))][j][k-1]),
max(maxi[i][j+(1<<(k-1))][k-1],maxi[i+(1<<(k-1))][j+(1<<(k-1))][k-1]));
mini[i][j][k]=min(min(mini[i][j][k-1],mini[i+(1<<(k-1))][j][k-1]),
min(mini[i][j+(1<<(k-1))][k-1],mini[i+(1<<(k-1))][j+(1<<(k-1))][k-1]));
}
}
}
//len=0;
//while((1<<(len+1))<t) ++len;
len=log2(t);
for(int i=1;i+t-1<=n;++i){
for(int j=1;j+t-1<=m;++j){
ans=min(ans,max(max(maxi[i][j][len],maxi[i+t-(1<<len)][j][len]),max(maxi[i][j+t-(1<<len)][len],maxi[i+t-(1<<len)][j+t-(1<<len)][len]))
-min(min(mini[i][j][len],mini[i+t-(1<<len)][j][len]),min(mini[i][j+t-(1<<len)][len],mini[i+t-(1<<len)][j+t-(1<<len)][len])));
}
}
printf("%d",ans);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1008;
int n,m,t;
int a[N][N],maxi[N][N],mini[N][N];
int q[N],pos[N],he,ta;
int main()
{
n=read();m=read();t=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
a[i][j]=read();
}
}
//----------------
for(int i=1;i<=n;++i){
he=1;ta=0;
for(int j=1;j<t;++j){
while(he<=ta&&a[i][j]>=q[ta]) --ta;
q[++ta]=a[i][j];
pos[ta]=j;
}
for(int j=t;j<=m;++j){
while(he<=ta&&pos[he]<=j-t) ++he;
while(he<=ta&&a[i][j]>=q[ta]) --ta;
q[++ta]=a[i][j];
pos[ta]=j;
maxi[i][j]=q[he];
}
}/*
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cout<<maxi[i][j]<<' ';
}cout<<'\n';
}
puts("");*/
for(int j=t;j<=m;++j){
he=1;ta=0;
for(int i=1;i<t;++i){
while(he<=ta&&maxi[i][j]>=q[ta]) --ta;
q[++ta]=maxi[i][j];
pos[ta]=i;
}
for(int i=t;i<=n;++i){
while(he<=ta&&pos[he]<=i-t) ++he;
while(he<=ta&&maxi[i][j]>=q[ta]) --ta;
q[++ta]=maxi[i][j];
pos[ta]=i;
maxi[i][j]=q[he];
}
}/*
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cout<<maxi[i][j]<<' ';
}cout<<'\n';
}
puts("");*/
//--------------------------
for(int i=1;i<=n;++i){
he=1;ta=0;
for(int j=1;j<t;++j){
while(he<=ta&&a[i][j]<=q[ta]) --ta;
q[++ta]=a[i][j];
pos[ta]=j;
}
for(int j=t;j<=m;++j){
while(he<=ta&&pos[he]<=j-t) ++he;
while(he<=ta&&a[i][j]<=q[ta]) --ta;
q[++ta]=a[i][j];
pos[ta]=j;
mini[i][j]=q[he];
}
}/*
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cout<<mini[i][j]<<' ';
}cout<<'\n';
}
puts("");*/
for(int j=t;j<=m;++j){
he=1;ta=0;
for(int i=1;i<t;++i){
while(he<=ta&&mini[i][j]<=q[ta]) --ta;
q[++ta]=mini[i][j];
pos[ta]=i;
}
for(int i=t;i<=n;++i){
while(he<=ta&&pos[he]<=i-t) ++he;
while(he<=ta&&mini[i][j]<=q[ta]) --ta;
q[++ta]=mini[i][j];
pos[ta]=i;
mini[i][j]=q[he];
}
}
/*for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cout<<mini[i][j]<<' ';
}cout<<'\n';
}
puts("");*/
int ans=INT_MAX;
for(int i=t;i<=n;++i){
for(int j=t;j<=m;++j){
ans=min(ans,maxi[i][j]-mini[i][j]);
}
}
printf("%d",ans);
return 0;
}